#![feature(alloc)]
#![feature(raw_vec_internals)]
extern crate alloc;

use std::ptr;
use std::mem;
use std::cmp;
use alloc::raw_vec::RawVec;

/// Copy minimum dependency code to reproduce bug.
#[cfg(target_pointer_width = "64")]
const MAXIMUM_ZST_CAPACITY: usize = 1 << (64 - 1); // Largest possible power of two
const MINIMUM_CAPACITY: usize = 1; // 2 - 1

pub struct FakeVecDeque<T> {
    // tail and head are pointers into the buffer. Tail always points
    // to the first element that could be read, Head always points
    // to where data should be written.
    // If tail == head the buffer is empty. The length of the ringbuffer
    // is defined as the distance between the two.
    tail: usize,
    head: usize,
    buf: RawVec<T>,
}

/// Calculate the number of elements left to be read in the buffer
#[inline]
fn count(tail: usize, head: usize, size: usize) -> usize {
    // size is always a power of 2
    (head.wrapping_sub(tail)) & (size - 1)
}

fn wrap_index(index: usize, size: usize) -> usize {
    // size is always a power of 2
    debug_assert!(size.is_power_of_two());
    index & (size - 1)
}

impl <T> FakeVecDeque<T> {
    /// Marginally more convenient
    #[inline]
    fn ptr(&self) -> *mut T {
        self.buf.ptr()
    }

    /// Marginally more convenient
    #[inline]
    fn cap(&self) -> usize {
        if mem::size_of::<T>() == 0 {
            // For zero sized types, we are always at maximum capacity
            MAXIMUM_ZST_CAPACITY
        } else {
            self.buf.cap()
        }
    }

    pub fn with_capacity(n: usize) -> FakeVecDeque<T> {
        // +1 since the ringbuffer always leaves one space empty
        let cap = cmp::max(n + 1, MINIMUM_CAPACITY + 1).next_power_of_two();
        assert!(cap > n, "capacity overflow");

        FakeVecDeque {
            tail: 0,
            head: 0,
            buf: RawVec::with_capacity(cap),
        }
    }


    /// Moves an element out of the buffer
    #[inline]
    unsafe fn buffer_read(&mut self, off: usize) -> T {
        ptr::read(self.ptr().offset(off as isize))
    }

    /// Writes an element into the buffer, moving it.
    #[inline]
    unsafe fn buffer_write(&mut self, off: usize, value: T) {
        ptr::write(self.ptr().offset(off as isize), value);
    }

    pub fn is_empty(&self) -> bool {
        self.tail == self.head
    }

    /// Returns `true` if and only if the buffer is at full capacity.
    #[inline]
    fn is_full(&self) -> bool {
        self.cap() - self.len() == 1
    }

    /// Returns the index in the underlying buffer for a given logical element
    /// index + addend.
    #[inline]
    fn wrap_add(&self, idx: usize, addend: usize) -> usize {
        wrap_index(idx.wrapping_add(addend), self.cap())
    }

    /// Returns the index in the underlying buffer for a given logical element
    /// index - subtrahend.
    #[inline]
    fn wrap_sub(&self, idx: usize, subtrahend: usize) -> usize {
        wrap_index(idx.wrapping_sub(subtrahend), self.cap())
    }

    #[inline]
    pub fn len(&self) -> usize {
        count(self.tail, self.head, self.cap())
    }

    #[inline]
    pub fn capacity(&self) -> usize {
        self.cap() - 1
    }

    /// Copies a contiguous block of memory len long from src to dst
    #[inline]
    unsafe fn copy_nonoverlapping(&self, dst: usize, src: usize, len: usize) {
        debug_assert!(dst + len <= self.cap(),
                      "cno dst={} src={} len={} cap={}",
                      dst,
                      src,
                      len,
                      self.cap());
        debug_assert!(src + len <= self.cap(),
                      "cno dst={} src={} len={} cap={}",
                      dst,
                      src,
                      len,
                      self.cap());
        ptr::copy_nonoverlapping(self.ptr().offset(src as isize),
                                 self.ptr().offset(dst as isize),
                                 len);
    }

    /// Frobs the head and tail sections around to handle the fact that we
    /// just reallocated. Unsafe because it trusts old_cap.
    #[inline]
    unsafe fn handle_cap_increase(&mut self, old_cap: usize) {
        let new_cap = self.cap();

        // Move the shortest contiguous section of the ring buffer
        //    T             H
        //   [o o o o o o o . ]
        //    T             H
        // A [o o o o o o o . . . . . . . . . ]
        //        H T
        //   [o o . o o o o o ]
        //          T             H
        // B [. . . o o o o o o o . . . . . . ]
        //              H T
        //   [o o o o o . o o ]
        //              H                 T
        // C [o o o o o . . . . . . . . . o o ]

        if self.tail <= self.head {
            // A
            println!("A");
            // Nop
        } else if self.head < old_cap - self.tail {
            // B
            println!("Copy into index: {} with {} elements, index boundary: {}",
                     old_cap, self.head, self.cap());
            self.copy_nonoverlapping(old_cap, 0, self.head);
            self.head += old_cap;
            /**
             * You will see head = 67, buf cap = 64 here
             */
            println!("After B: head: {}, tail: {}, ", self.head, self.tail);
            debug_assert!(self.head > self.tail);
        } else {
            // C
            println!("C");
            let new_tail = new_cap - (old_cap - self.tail);
            self.copy_nonoverlapping(new_tail, self.tail, old_cap - self.tail);
            self.tail = new_tail;
            debug_assert!(self.head < self.tail);
        }
        debug_assert!(self.head < self.cap());
        debug_assert!(self.tail < self.cap());
        debug_assert!(self.cap().count_ones() == 1);
    }

    /// Buggy code
    pub fn reserve_bug(&mut self, additional: usize) {
        let old_cap = self.cap();
        let used_cap = self.len() + 1;
        let new_cap = used_cap.checked_add(additional)
            .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
            .expect("capacity overflow");

        // Yilun: Fix is around here
        println!("used_cap: {}, old_cap: {}, new_cap:{}, capacity: {}",
                 used_cap, old_cap, new_cap, self.capacity());
        if new_cap > self.capacity() {
            self.buf.reserve_exact(used_cap, new_cap - used_cap);
            unsafe {
                self.handle_cap_increase(old_cap);
            }
        }
    }

    /// Patched code
    pub fn reserve_patch(&mut self, additional: usize) {
        let old_cap = self.cap();
        let used_cap = self.len() + 1;
        let new_cap = used_cap.checked_add(additional)
            .and_then(|needed_cap| needed_cap.checked_next_power_of_two())
            .expect("capacity overflow");

        if new_cap > old_cap {
            self.buf.reserve_exact(used_cap, new_cap - used_cap);
            unsafe {
                self.handle_cap_increase(old_cap);
            }
        }
    }

    #[inline]
    fn grow_if_necessary(&mut self) {
        if self.is_full() {
            let old_cap = self.cap();
            self.buf.double();
            unsafe {
                self.handle_cap_increase(old_cap);
            }
            debug_assert!(!self.is_full());
        }
    }

    pub fn pop_front(&mut self) -> Option<T> {
        if self.is_empty() {
            None
        } else {
            let tail = self.tail;
            self.tail = self.wrap_add(self.tail, 1);
            unsafe { Some(self.buffer_read(tail)) }
        }
    }

    pub fn push_back(&mut self, value: T) {
        self.grow_if_necessary();

        let head = self.head;
        self.head = self.wrap_add(self.head, 1);
        unsafe {
            // println!("Try to write to index: {}, current buf capacity: {}", head, self.buf.cap());
            self.buffer_write(head, value);
        }
    }

    // Yilun implement
    pub fn dump(&self) {
        println!("head: {}, tail: {}, cap: {}", self.head, self.tail, self.cap());
    }
}

/**
 * How to reproduce this bug.
 *    - This bug need to be reproduced in release build
 *    - cargo run --release
 */

fn main() {
    let mut deque = FakeVecDeque::with_capacity(32);
    // deque.push_front(0); // push front actually not working
    /**
     * Construct a case that could trigger the bug
     */
    for i in 0..32 {
        deque.push_back(0);
        deque.pop_front();
    }
    for i in 0..35 {
        deque.push_back(0);
    }
    deque.dump();


    deque.reserve_bug(10);
    // deque.reserve_patch(10);
    deque.push_back(0);
}
